package alist;

public class MyLinkedList {
    public ListNode head;

    public void creatList() {
        ListNode listNode1 = new ListNode(21);
        ListNode listNode2 = new ListNode(22);
        ListNode listNode3 = new ListNode(22);
        ListNode listNode4 = new ListNode(22);
        ListNode listNode5 = new ListNode(22);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        this.head = listNode1;
    }

    public void disPlay() {
        ListNode cur = this.head;
        if (isEmpty()) {
            System.out.println("链表为空!");
            return;
        }
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    public void display2(ListNode listNode) {

        ListNode cur = listNode;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }

    }
    //头插
    public void addFirst(int data) {
        ListNode newListNode = new ListNode(data);
        if (isEmpty()) {
            this.head = newListNode;
            return;
        }
        newListNode.next = this.head;
        this.head = newListNode;
    }

    //尾插
    public void addEnd(int data) {

        ListNode newListNode = new ListNode(data);
        ListNode cur = this.head;

        if (isEmpty()) {
            this.head = newListNode;
            return;
        }
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = newListNode;

    }

    /**
     * 寻找下标
     *
     * @param index
     * @return
     */
    public ListNode findIndex(int index) {
        ListNode cur = this.head;
        while (--index > 0) {
            cur = cur.next;
        }
        return cur;

    }

    //任意位置插入   0下标开始
    public void addIndex(int index, int data) {
        ListNode newListNode = new ListNode(data);
        if (index == 0) {
            addFirst(data);
            return;
        }
        if (index > size()) {
            System.out.println("插入位置错误!");
            return;
        }
        ListNode cur = findIndex(index);
        newListNode.next = cur.next;
        cur.next = newListNode;

    }

    //找出第一次出现key的节点
    public ListNode findDelListNode(int data) {
        ListNode del = this.head;
        /*while (del.val != data) {
            del = del.next;
        }
        return del;*/
        while (del != null) {
            if (del.val == data) {
                return del;
            }
            del = del.next;
        }
        return null;
    }


    //删除第一次出现的key的节点
    public void delListNode(int data) {
        ListNode cur = this.head;
        ListNode del = findDelListNode(data);
        if (del == null) {
            System.out.println("链表中没有这个数 !!");
            return;
        }
        if (isEmpty()) {
            System.out.println("链表为空!");
            return;
        }
        if (del == this.head) {
            this.head = this.head.next;
            return;
        }
        while (cur.next != del) {
            cur = cur.next;
        }
        cur.next = del.next;
        del.next = null;
    }

    //删除所有出现的key数字
    public void delskey(int data) {
        if (isEmpty()) {
            System.out.println("链表为空");
            return;
        }

        ListNode cur = this.head;
        ListNode del = this.head.next;

        while (del != null) {
            if (del.val == data) {
                cur.next = del.next;
                del = del.next;
            } else {
                cur = del;
                del = del.next;
            }
        }
        if (this.head.val == data) {
            this.head = this.head.next;
            return;
        }
    }



    //释放链表
    public void clean() {
//        this.head = null;
        ListNode cur = this.head.next;
        while (cur != null) {
            this.head.next = null;
            this.head = cur;
            cur = cur.next;
        }




    }

    // 反转链表
    public void reverseListNode() {
        if (isEmpty()) {
            System.out.println("链表为空");
            return;
        }

        ListNode cur = this.head;
        ListNode curNext = this.head.next;
        ListNode tep;

        while (curNext != null) {
            tep = curNext.next;
            curNext.next = cur;
            cur = curNext;
            curNext = tep;
        }
        this.head.next = null;
        this.head = cur;
    }

    //求中间节点
    public ListNode  middleListNode() {
        ListNode fast = this.head;
        ListNode slow = this.head;

        //1
        while (fast.next != null ) {
            fast = fast.next;
            slow = slow.next;
            if (fast.next == null) {
                break;
            }
            fast = fast.next;
        }
        //2
        /*while (fast != null && fast.next !=null) {  //fast != null && fast.next !=null 不能更改顺序  否则空指针异常
            fast = fast.next.next;
            slow = slow.next;
        }*/

        return slow;
    }

    //求倒数第k个节点
    public ListNode bottomListNode(int k) {
        if (k < 0) {
            return null;
        }
        ListNode fast = this.head;
        ListNode slow = this.head;
        while(--k > 0) {
            fast = fast.next;
            if (fast == null) {     //用于判断k是否越界
                System.out.println("错误");
                return null;
            }
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    //将两个升序链表合为一个
    public ListNode mergeListNode(ListNode listNode1, ListNode listNode2) {
        ListNode newListNode = new ListNode(0);
        ListNode kep = newListNode;
        while (listNode1 != null && listNode2 != null){
            if(listNode1.val < listNode2.val) {
                kep.next = listNode1;
                kep = listNode1;
                listNode1 = listNode1.next;
            } else {
                kep.next = listNode2;
                kep = listNode2;
                listNode2 = listNode2.next;
            }
        }
        if (listNode1 == null) {
            kep.next = listNode2;
        }
        if (listNode2 == null) {
            kep.next = listNode1;
        }
        return newListNode.next;
    }

    //找出比x小的数放到链表前列(保持顺序不变)
    public void sortListNode(int x) {
        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;
        ListNode cur = this.head;

        while (cur != null) {
            if(cur.val < x) {
                //第一次
                if (bs == null) {
                    bs = cur;
                    be = cur;
                   // cur = cur.next;
                }
                //非第一次
                else {
                    be.next = cur;
                  //  cur = cur.next;
                    be = be.next;
                }

            } else {
                //第一次
                if (as == null) {
                    as = cur;
                    ae = cur;
                   // cur = cur.next;
                }
                //非第一次
                else {
                    ae.next = cur;
                    ae = cur;
                   // cur = cur.next;
                }
            }
            cur = cur.next;
        }
        //预防第一个段为空
        if (bs == null) {
            this.head = as;
            return;
        }


        /*if (as == null) {
            be.next = null;
            this.head = bs;
            return;
        }
        be.next = as;
        ae.next = null;*/

        be.next = as;
        //预防第二段不为空
        if (as != null) {
            ae.next = null;
        }

        this.head = bs;
    }


    //删除重复数字
    public ListNode deleteDuplication() {
        ListNode cur = this.head;
        ListNode newListNode = new ListNode(1);
        ListNode kep = newListNode;
        while (cur != null) {
            if (cur.next != null && (cur.val == cur.next.val)) {
                while (cur.next != null && (cur.val == cur.next.val)) {
                    cur = cur.next;
                }
                cur = cur.next;
            } else {
                kep.next = cur;
                kep = cur;
                cur = cur.next;
            }
        }
        kep.next = null;
        return newListNode.next;
    }


    //判断是否为空链表
    public boolean isEmpty() {
        return this.head == null ? true : false;
    }

    public int size() {
        int count = 0;
        ListNode cur = this.head;
        while (cur != null) {
            cur = cur.next;
            count++;
        }
        return count;
    }

}

































